import unittest
from typing import List


class Solution:
    def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:
        # 求会议间的空余时间段数组rest
        rest = []
        if startTime[0] != 0:
            rest.append(startTime[0])
        else:
            rest.append(0)
        for idx in range(1, len(startTime)):
            rest.append(startTime[idx] - endTime[idx - 1])
        if endTime[len(endTime) - 1] < eventTime:
            rest.append(eventTime - endTime[len(endTime) - 1])
        else:
            rest.append(0)

        # 求会议空间占用时间数组
        meeting = [endTime[idx] - startTime[idx] for idx in range(0, len(endTime))]
        left_right = [rest[0]]
        for idx in range(1, len(rest)):
            left_right.append(max(left_right[idx - 1], rest[idx]))

        right_left = [0] * len(rest)
        right_left[-1] = rest[-1]
        for idx in range(len(rest) - 2, 0 - 1, -1):
            right_left[idx] = max(right_left[idx + 1], rest[idx])

        # print("meeting: ", meeting)
        # print("rest: ", rest)
        # print("left_right: ", left_right)
        # print("right_left: ", right_left)

        meeting_move = [False] * len(meeting)
        for idx in range(0, len(meeting)):
            if len(left_right) < 3:
                break
            if idx == 0:
                meeting_move[idx] = right_left[idx + 2] >= meeting[idx]
                continue
            if idx == len(meeting) - 1:
                meeting_move[idx] = left_right[idx - 1] >= meeting[idx]
                continue
            meeting_move[idx] = left_right[idx - 1] >= meeting[idx] or right_left[idx + 2] >= meeting[idx]

        # print(meeting_move)

        # 普通场景，等价于定长滑动窗口
        ret = 0
        for idx in range(0, len(rest) - 1):
            cur = rest[idx] + rest[idx + 1]
            if meeting_move[idx]:
                cur += meeting[idx]
            if cur > ret:
                ret = cur
        return ret


class Test(unittest.TestCase):
    def test_case1(self):
        solution = Solution()
        target = solution.maxFreeTime(10, [0, 7, 9], [1, 8, 10])
        self.assertEqual(target, 7)

    def test_case2(self):
        solution = Solution()
        target = solution.maxFreeTime(21, [7,10,16], [10,14,18])
        self.assertEqual(target, 10)
